package Arrays;

/**
 * 209 最小长度子数组
 * 给定一个含有 n 个正整数的数组和一个正整数 target 。
 * 找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
 */
public class minSubArrayLen {
    /**
     * 滑动窗口的经典例题
     * 窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
     * 窗口的起始位置如何移动：如果当前窗口的值大于等于s了，窗口就要向前移动了（也就是该缩小了）。
     * 窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引
     *
     * 不需要考虑结果被遗漏的情况，因为在前面第一次大于target的时候就已经记录下了，所以后面如果有更小的会更新。
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {

        if (nums == null || nums.length == 0) return 0;
        int res = Integer.MAX_VALUE;
        int sum = 0;
        int start = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            while (sum >= target) {
                res = Math.min(res, i - start + 1);
                sum -= nums[start++];
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}
